package algorithm.sort;

import java.util.Arrays;

/**
 * @Author liuhaoqi
 * @Date 2020/12/31 14:58
 * @Version 1.0
 * 归并排序
 */
public class MergeSort2 {
    public static void main(String[] args) {
        int[] arr = {3, 10, 22, 2, 1, 5, 9, 12, 1, 9, 7, 6, 5, 4, 3, 2, 1};
//        mergeSort(arr);
        mergeSort2(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 迭代 的归并排序
     *
     * @param arr
     */
    public static void mergeSort(int[] arr) {
        if (arr.length < 1) {
            return;
        }
        for (int step = 2; step / 2 <= arr.length; step *= 2) {
            for (int i = 0; i < arr.length; i += step) {
                int mid = i + step / 2 - 1;
                if (mid + 1 <= arr.length - 1) {//说明该子区间的右子区间还有元素 mid+1是该步长区间内 右子区间的开始位置
                    //i + step - 1 是 该步长区间以左子区间开始元素 加上步长后的最大值
                    merge(arr, i, mid, mid + 1, Math.min(i + step - 1, arr.length - 1));
                }
            }
        }
    }

    /**
     * 递归版本 的归并排序
     *
     * @param arr
     */
    public static void mergeSort2(int[] arr) {
        if (arr.length < 1) return;
        sort(arr, 0, arr.length - 1);
    }

    public static void sort(int[] arr, int left, int right) {
        if (left >= right)
            return;
        // 找出中间索引
        int center = (left + right) / 2;
        // 对左边数组进行递归
        sort(arr, left, center);
        // 对右边数组进行递归
        sort(arr, center + 1, right);
        // 合并
        merge(arr, left, center, center + 1, right);

    }


    //公用的merge方法
    public static void merge(int[] arr, int leftBegin, int leftEnd, int rightBegin, int rightEnd) {
//        int[] temp = new int[rightEnd - leftBegin + 1];
        int[] temp = new int[rightEnd - leftBegin + 1];
        int i = leftBegin;
        int j = rightBegin;
        int index = 0;
        while (i <= leftEnd && j <= rightEnd) {
            if (arr[i] >= arr[j]) {
                temp[index++] = arr[j++];
            } else {
                temp[index++] = arr[i++];
            }
        }
        while (i <= leftEnd) {
            temp[index++] = arr[i++];
        }
        while (j <= rightEnd) {
            temp[index++] = arr[j++];
        }
        System.arraycopy(temp, 0, arr, leftBegin, index);
    }
}



